# -*- coding:utf-8
# 5383. 给 N x 3 网格图涂色的方案数 显示英文描述
# 用户通过次数0
# 用户尝试次数0
# 通过次数0
# 提交次数0
# 题目难度Hard
# 你有一个 n x 3 的网格图 grid ，你需要用 红，黄，绿 三种颜色之一给每一个格子上色，且确保相邻格子颜色不同（也就是有相同水平边或者垂直边的格子颜色不同）。
#
# 给你网格图的行数 n 。
#
# 请你返回给 grid 涂色的方案数。由于答案可能会非常大，请你返回答案对 10^9 + 7 取余的结果。

class Solution:
    def numOfWays(self, n: int) -> int:
        mod = int(1e9 + 7)
        s = ['ryr', 'ryg', 'rgr', 'rgy', 'yry', 'yrg', 'ygr', 'ygy', 'gry', 'grg', 'gyr', 'gyg']
        ans = {a : 1 for a in s}
        for i in range(n - 1):
            newans = {a : 0 for a in s}
            for i in s:
                for j in s:
                    if all(a != b for a, b in zip(i, j)):
                        newans[i] += ans[j]
                        newans[i] %= mod
            ans = newans
        return sum(ans.values()) % mod